(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "A computer based classification of caps in PG(4,2)"

(N 

o 

(N 



in 

O 

u 



A computer based classification of caps in 

PG(4, 2; 



Daniele Bartoli, Stefano Marcugini, Fernanda Pambianco 



Abstract 



^ [ In this paper we present the complete classification of caps in PG(4, 2). These results 

have been obtained using a computer based exhaustive search that exploits projective 
equivalence. 

> 

Q^ ' 1 Introduction 

p 

^ ' 3 of which are collinear. A n-cap is called complete if it is not contained in a (n + l)-cap. 

^ . For a detailed description of the most important properties of these geometric structures, 

we refer the reader to [4j . In the last decades the problem of determining the spectrum of 
the sizes of complete caps has been the subject of a lot of researches. For a survey see [I]. 

K^ I In [5] (see Th. 18.2.1) is presented the classification of complete caps in PG{3,2) and it is 

H ' also possible to understand the classification of the incomplete caps. The following table 

" " " shows the number of non equivalent complete and incomplete caps in PG{3, 2). 



In the projective space PG{r, q) over the Galois Field GF{q), a ri-cap is a set of n points no 



Table 1: Number and type of non equivalent examples 



/C| 


# COMPLETE 
CAPS 


# INCOMPLETE 
CAPS 


5 
6 

7 
8 


1 



1 


1 
1 
1 




In this work we search for the classification of complete and incomplete caps in PG{A, 2), 
using an exhaustive search algorithm. In Section |2] the algorithm utilized is illustrated; in 
Section [3] the complete list of non equivalent complete and incomplete caps is presented. 



2 The searching algorithm 

In this section the algorithm utilized is presented. Our goal is to obtain the classification 
of complete and incomplete caps in FG(4,2). It is not restrictive to suppose that a cap in 
PG{4, 2) contains this five points: 

7^ = {(1 : : : : 0); (0 : 1 : : : 0); (0 : : 1 : : 0); (0 : : : 1 : 0); (0 : : : : 1)}. 

Then we define the set Cand of all the points lying no 2-secant of 7^. We introduce in Cand 
the following equivalence relationship: 



F~g 



CU{P}^CU{Q}, 



where = means that the two sets are projectively equivalent. This relationship spreads the 
candidates in equivalent classes Ci, . . . ,Ck- 

The choice of the next point to add to the building cap can be made only among the repre- 
sentatives of the equivalent classes, in fact two caps one containing C U {P} and the other 
one C U {Q}, with P and Q in Cj, are equivalent by definition of orbit. 
Suppose now that we have construct all the caps containing CU{Pj}, with i < i. Considering 
the caps containing C U {Pj} with i < j, all the points of the classes Ck with k < i can be 
avoided. In fact a cap containing C U {Pj} U {Pk}, with P^ G Ck and k < i, is projectively 
equivalent to a cap containing C U {Pk} U {Pj}, already studied. 

When we add a new point to the cap, we can divide all the remaining candidates in equiv- 
alence classes, as above. Two points P and Q are in relationship with the j-th class Cj, i.e. 



P ~j Q, if C U {Pj} U {P} and C U {Pj} U {Q} are projectively equivalent. 
At the m-th step of the extension process if the cap C U {Pi^} U . . . U |p^*i---*™-i j u |pj jg 
projectively equivalent to the cap C U {Pi^} U . . . U {/^^■■■^™"'} U {Q} with Pji-^'' G C^i-*'-, 
then P and Q are in relationship {P ^i^...im Q) and they belong to the same class Cl^^'^l"". 
Iterating the process we can build a tree similar to the following: 



Ci 



Co 



Ch 



CI 






CI 






cf 






Cl'^ 



c 



1,1 



Cl'' 



c 



2,1 

fc2,l 



c« 






nk,kk 



The tree is important to restrict the number of candidates in the extension process. Suppose 
that we have generated a n-cap containing the cap C U {Pi^ } U {P/^ } U . . . U {P/^"'*™"^ } U {P}, 
after having generated n-caps containing C U {Pj} with j < ii, C U {Pi^} U [P]^} with 
i < 22,. . . , C U {PiJ U {P*;!} U . . . U {p^i-^— 1} with j < i„, with P;!-^- G C^-*'-. Then the 



uc: 



^m -1- 



can 



points belonging to Ci U . . . U Ci,_i U C}^ U . . . U CY^_^ U . . . U C^ '""^ U 
be avoided, because a cap containing one of them is equivalent to one already found. For 
example a n-cap containing C U {P^ J U . . . U {Pt"^"'""'^} U {P} U {Q} with Q eCh for some 
/i < «! is equivalent to a n-cap containing C U {Pfe}, which is already found. 



3 Results 

In this Section all non equivalent caps, complete and incomplete, in PG'(4, 2) are presented. 

3.1 Non-equivalent caps /C in PG(4, 2) 

This table shows the number and the type of the non equivalent examples of all the caps. 



Table 2: Number and type of non equivalent examples 



/C| 


# COMPLETE 


# INCOMPLETE 




CAPS 


CAPS 


6 





3 


7 





3 


8 





4 


9 


1 


4 


10 


1 


3 


11 





2 


12 





2 


13 





1 


14 





1 


15 





1 


16 


1 






All the non equivalent examples of the caps described in the table above are presented. 
In particular for each cap we compute the stabilizer and the weight enumerators of the 
associated code. 



Size 


Type 


Cap 


Weight enumerators 


G 


6 


Inc. 


10 1 
10 1 
10 1 
10 1 
11 


21541551 


G720 


6 


Inc. 


10 10 
10 
10 10 
110 
11 


112103104555 


G120 


6 


Inc. 


10 1 
10 
10 1 
10 1 
10 


^227312475251 


G48 


7 


Inc. 


10 10 
10 1 
10 10 
10 11 
10 1 


2639495671 


Gj2 


7 


Inc. 


10 11 
10 10 
10 1 
10 11 
110 


26312475453 


G4S 


7 


Inc. 


110 1 
110 
10 10 1 
10 1 
10 


Ii233"4ii536i7i 


G48 


8 


Inc. 


1110 1 
10 10 
110 10 1 
10 1 
10 10 


244225431 


G384 


8 


Inc. 


110 1 
1110 
10 110 1 
10 10 1 
10 


^137414577131 


GIQ8 


8 


Inc. 


110 11 
110 10 
10 10 1 
10 11 
110 


2I310411545372 


G48 


8 


Inc. 


110 10 
110 1 
10 10 10 
10 11 
10 1 


2238410585231 


G32 



Size 


Type 


Cap 


Weight enumerators 


G 


9 


Inc. 


110 11 
1110 10 
10 110 1 
10 10 11 
000000100 


114145143191 


^1334 


9 


Inc. 


111000011 
110 10 
110 10 1 
10 11 
10 110 


34414587431 


Gi92 


9 


Inc. 


110 10 
110 1 
10 110 10 
110 11 
10 10 1 


3649595691 


Gr72 


9 


Inc. 


1110 10 
110 1 
110 10 10 
10 11 
10 10 1 


3133411511537191 


6*48 


9 


Comp. 


110 11 
1110 10 
10 110 1 
10 10 11 
110 


214215732 


^336 


10 


Inc. 


110 110 
110 10 1 
10 110 10 
110 11 
10 110 1 


415515^01 


^720 


10 


Inc. 


10 110 11 
10 111 
0010011011 
10 110 1 
110 10 1 


21465165631^0! 


^384 


10 


Inc. 


10 10 10 
0100001110 
0010010111 
0001011011 
10 10 1 


32475125772101 


6*48 


10 


Comp. 


1100001011 
10 10 10 1 
10 1111 
10 10 110 
10 1110 


41051635 


^1920 


11 


Inc. 


10 110 10 1 
10 1111 
00100110111 
10 110 11 
110 10 1 


31425125127231111 


^192 


11 


Inc. 


110 10 10 
110 1110 
10 10 111 
10 110 11 
10 10 10 1 


4551051075111 


G120 



Size 


Type 


Cap 


Weight enumerators 


G 


12 


Inc. 


100001101101 
010000011111 
001001100111 
000100111011 
000011010001 


43Q2483121 


^2304 


12 


Inc. 


110000101001 
011000011101 
000100101111 
000010110111 
010001010011 


4158Q127881121 


^192 


13 


Inc. 


1000011011001 
0100000111101 
0010011001111 
0001001110111 
0000110100011 


53gl27l283i3l 


^576 


14 


Inc. 


11000011011001 
01100000111101 
00010011001111 
00001001110111 
01000110100011 


Q771687141 


^2688 


15 


Inc. 


110000111011001 
011000000111101 
000100110001111 
000010011110111 
010001101100011 


715315151 


^20160 


16 


Comp. 


1100001110110001 
0110000001111101 
0001001100011111 
0000100111100111 
0100011011001011 


gSOlQl 


^322560 



References 

[1] A. Davydov, G. Faina, S. Marcugini and F. Pambianco, On size of complete caps in projective 
spaces PG{n, q) and arcs in planes PG{2, q), Journal of Geometry, published online 18/7/2009. 

[2] G. Faina, S. Marcugini, A. Milani and F. Pambianco, The size k of the complete fe-caps in 
PG{n,q) for small q and 3 < n < 5, Ars Combinatoria 50 (1998), 235-243. 

[3] M. Hall and J. K. Senior, The group of order 2" (n < 6), Macmillan, New York, 1964. 

[4] J. W. P. Hirschfeld, Projective geometries over finite fields, Claredon Press, Oxford, 1979. 

[5] J. W. P. Hirschfeld, Finite projective spaces of three dimension, Claredon Press, Oxford, 1985.